1. Field of the Invention
This invention relates to switching systems employing nonhierarchical routing and, more particularly, to systems where the routing is a function of traffic load conditions.
2. Description of the Prior Art
The U.S. telecommunications toll network includes a large number of switching offices and trunk lines interconnecting those offices. Since these elements of the network are expensive, designers of the tool network have always striven to employ as few offices and trunks as possible. Thus, it has long been established that a network may be designed with fewer trunks than is required to guarantee a path from any office to any other office regardless of network load. The rationale for this is that customers are willing to tolerate call blocking as long as it occurs infrequently. A telecommunication network that permits call blocking is able to more efficiently utilize its resources.
To minimize blocking with a given amount of resources, the network must be given structure and efficient path selection algorithms. Until recently, the U.S. telecommunications network has been structured in a hierarchical fashion. Offices were ranked by class (1 through 5) and a routing plan was employed that directed the switching from one office to another based on the respective ranking of the offices. This hierarchical structure served well for many years.
In an effort to minimize blocking in the hierarchical structure, various arrangements and algorithms exist for determining appropriate routes. One such arrangement is described by Szybicki et al. in U.S. Pat. No. 4,284,852, issued Aug. 18, 1981. In accordance with the Szybicki et al. arrangement, a plurality of switching end offices (class 5 offices) are grouped into a cluster, with each switch in the cluster having direct trunk lines to all other switching offices in the cluster. In addition, all of the switching offices have trunks to a tandem office, data links to a logic device, and memory for storing routing information. A call can originate or terminate at any office and, therefore, each office stores within its memory the first path choice to all other offices; that choice being the direct trunk connecting the offices. In addition to each first path choice, the logic device provides to each switching office information regarding alternate routes within the cluster of switching offices. The alternate route information, which is also stored in memory within the switching offices and used when the office is the originating office, is derived by the logic device from information supplied by the data links. When no available path is found within the cluster, the originating switch attempts to establish a path through the tandem office, and when that fails, the call is blocked.
To more effectively minimize network costs and also minimize blocking a new structure is currently being implemented in the AT&T Communications network which includes a new routing technique called Dynamic Nonhierarchical Routing. The new structure no longer ranks the toll offices, and paths between switching offices are established based on routing sequences stored in each of the (originating) toll offices. One description of a dynamic nonhierarchical arrangement for routing traffic is described in my U.S. Pat. No. 4,345,116 issued Aug. 17, 1982. Additional descriptive material is found in, "Design and Optimization of Networks With Dynamic Routing," by Ash et al., and "Servicing and Real-Time Control of Networks With Dynamic Routing," by Ash et al., both in The Bell System Technical Journal, Vol. 60, No. 8, October 1981, pp. 1787-1846. FIG. 1 is descriptive of my previously disclosed arrangement.
In FIG. 1, the telecommunication network, represented by block 410, includes switching offices 310 through 315 and interconnecting trunk groups (links) 316 through 326. There is no hierarchical designation to switches 310 through 315 although they are drawn to imply that in the old hierarchical routing arrangement switching offices 310 and 315 were the Primary Centers, switching offices 311 and 314 were the Sectional Centers and switching offices 312 and 313 were the Regional Centers.
Switches 310-315 are stored program control switches, which means that they have memory and that at least some of their switching functions are controlled by the memory contents. Specifically in connection with my prior art nonhierarchical arrangement, each of the switches contains memory for storing information regarding the trunk links between itself and other switches, and information regarding the routing sequences available for establishing a path. Path choices are made by the switching offices in accordance with the stored information.
To effect a connection between switching office 311 and switching office 314, a direct path may be established via link 321. A path may also be established via switching office 312 (links 319 and 317), via office 310 (links 324 and 323), via office 313 (links 318 and 320) or via office 315 (links 322 and 325). Still additional paths may be established by using more than one office (e.g., link 319, office 312, link 316, office 313 and link 320). In accordance with the described nonhierarchical dynamic routing arrangement, switching office 311 contains in its memory a "map", or table, of the link sizes (number of trunks in the trunk group) between itself and its neighboring offices and a table of routing sequences for use at different time periods during the day containing the sequence for establishing connections with switching office 314 (as well as sequences for establishing connections with other offices). The routing sequence identifies the first route choice and subsequent route choices, e.g., first choice being path 321 and subsequent choices being path 319-312-317, then path 318-313-320, then path 322-315-325. The first choice path is selected unless all of the trunks in that path are busy. When that condition is encountered, path 319-312-317 is selected unless all of its trunks are also busy. Only when all paths in the routing sequence are found busy is the call blocked.
In the selection of multi-link paths (such as the path containing link 319, switching office 312, and link 317) it is possible for one of the links to be unavailable. When the first link is available but the second link is not, a "crankback" signal is sent back to the originating office so that a subsequent path in the sequence can be attempted.
From the above it should be appreciated that the link sizes and the route selection sequences are interrelated and that both are extremely important to the effective utilization of network resources. Hence, the system of FIG. 1 attempts to concurrently optimize both the design of the network and the design of the route selection sequence for use at different time periods during the day. It attempts to minimize the number of trunks in each link that is required in order to achieve a desired level of service and, concurrently, it determines the desired route selection sequences for the determined link sizes. These determinations are made in the processes described below.
While network 410 in FIG. 1 carries traffic, in accordance with my previously disclosed arrangement it also sends information concerning the carried traffic (e.g., call attempts and usage) to three processes which are identified in FIG. 1 by network designer block 430, demand servicer 450, and dynamic router 470. Each of the three is preceded by a traffic estimator (blocks 420, 440, and 460, respectively).
In the network designer arrangement of blocks 420 and 430, traffic is gathered over long intervals. The gathered traffic is used to determine the appropriate link sizes for the network to achieve a predetermined grade of service and the optimum route selection sequences for use at different time periods for the forecasted traffic load (which is based on projection factors and statistics derived from the previous gathering interval). A twice yearly cycle time for the gathering of information is quite appropriate for the network designer arrangement. The information developed by network designer 430 is used to efficiently allocate the physical resources that are already in the field as well as the planned construction.
In the demand servicer arrangement of blocks 440 and 450, traffic information is gathered with a shorter cycle time, perhaps weekly, and it is used to fine tune the link sizes to reflect changes in actual traffic demands which deviate from forecasted demands and cause unexpected service problems. Processes 430 and 450 also modify and update the routing sequences for use at different time periods during the day that each switch maintains.
In the dynamic router arrangement of blocks 460 and 470, even more frequent adjustments to the routing sequences are developed. The traffic information is gathered with a still shorter cycle time, perhaps hourly, and adjusted time sensitive routing sequences are developed that are a function of the currently anticipated traffic. Thus, the dynamic router arrangement of blocks 460 and 470 deals with load deviations from the loads estimated in blocks 420 and 440 that are actually experienced. This includes day-to-day load variations, unforecasted permanent increases in demand (until capacity is augmented per determinations made by the demand servicer arrangement), and network congestion under overload and failure conditions.
With the aforedescribed combination of elements we obtained an improved nonhierarchical arrangement for establishing alternate routing sequences responsive to variations in the traffic demand placed upon the links in the network. The improved arrangement permits the system to take advantage of noncoincident peak traffic loads on different routes.
As indicated above, my disclosed system receives traffic information (which are measurements of traffic load over a given time period) from the network. That information is very helpful in determining the needed total number of trunks that ought to be allocated for traffic to each office and is also helpful in determining the appropriate routing sequences. However, traffic information by itself does not reveal existing congestion on various paths when alternate paths handle the traffic and, consequently, routing sequences based on traffic measurements alone do not necessarily result in the selection of the most efficient routing sequences. Also, the present network designer process does not account for the fact that access to node-to-node traffic capacity (i.e., between any originating office and terminating office) is substantially more efficient with real-time traffic sensitive routing, which is responsive to both network status information and traffic information, in the nonhierarchical structure than with time sensitive routing, which is responsive only to traffic information. The result is a "required link size" determination in the prior art that is greater than necessary for real-time traffic sensitive routing.
It is an object of this invention to optimize the allocation of resources in the telecommunications network.
It is a further object of this invention to obtain additional information for each switching office in the network and to thereby improve the process of determining the appropriate link sizes and route selections in the network.
It is still another object of this invention to provide means for near real-time evaluation of the network load and to make the network route selections responsive to the network load in corresponding near real-time.